// 冲突检测
// xin 新皇后在行中的位置(列号), huangHouMen 已放置的皇后们
function chongtu(lie, huangHouMen) {
  // 同列检测,竖向冲突
  if (huangHouMen.includes(lie)) {
    return true
  }
  const hang = huangHouMen.length // 皇后们的个数即新皇后的行号
  for(let key in huangHouMen){  
    const hangH = Number(key)// hangH 为每个皇后所在的行号
    const lieH = huangHouMen[key]  // lieH 为第hangH行的皇后所在列号
    // console.log(typeof(lie), typeof(lieH), typeof(hang), typeof(hangH))
    // 逐行放,已保证了横向不冲突, 这里只需检测斜向冲突
    if ((lie - hang) === (lieH - hangH)) {
      // console.log("右上")
      // 右下方向
      return true
    }
    if ((hang + lie) === (hangH + lieH)){
      // console.log("右上")
      // 右上方向
      return true 
    }
  }
  return false
}

let cc = 0

// 递归版本
function build(n = 8, curr = []) {
  if (curr.length === n) {
    console.log(curr.join(','), ++cc)
  } else {
    for(let i = 0; i < n; i++) {
      if(!chongtu(i, curr)) {
        const ls = [...curr, i]
        build(n, ls)
      }
    }
  }
}
// build()

// 循环版本
function buildfor() {
  let rc = 0 // 答案个数
  const p = [] // 下标为行号,元素为该行皇后的位置
  let nextOver = false // 下一行已探索完了
  while (p.length === 0 || p[0] < 4) { // 第一行只探索前四个位置
    console.log("\n新的探索", p.join(','), nextOver ? '本行递进' : '下一行')
    let start = 0 // 要探索行的探索起始位置
    if (nextOver) { // 下一行探索完了
      // 当前的最后一个皇后可以淘汰,需在该行继续探索
      console.log("下一行探索完了", p.join(','))
      start = p.pop() + 1
      nextOver = false
    }
    // 如果皇后个数小于8
    while(p.length < 8 && !nextOver) {
      // 添加一个皇后
      console.log("在 [" , p.join(','), "] 之后,从", start, "始尝试添加一个新皇后")
      let sucess = false // 添加成功
      nextOver = true
      for(let i = start; i < 8; i++) {
        if (!chongtu(i, p)) {
          // 记录新皇后位置
          p.push(i)
          console.log("放入一个皇后", i)
          // 看看是否放够8个
          if (p.length === 8) {
            console.log(p.join(','), ++rc, 
              "----------------为了醒目---------------=========================") // 输出
          } else {
            nextOver = false // 告知需要探索下一行
            start = 0 // 下一行起始位置
          }
          break // 不需要看本行的下一个位置了
        }
      }
      console.log("结束尝试添加一个新皇后", p.join(','), nextOver, start)
    }
  }
  console.log("找到了", rc, "个答案")
}

buildfor()
